/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/first-missing-prime-number
   @Language: C++
   @Datetime: 19-06-05 10:42
   */

class Solution {
public:
	/**
	 * @param nums: an array of integer
	 * @return: the first missing prime number
	 */
	int firstMissingPrime(vector<int> &nums) {
		// write your code here
		if(nums.size()==0) return 2;
		vector<bool> primes(nums.back()+1,true);
		for(int i=2; i<primes.size(); ++i){
			if(!primes[i]) continue;
			for(int j=i+i; j<primes.size(); j+=i)
				primes[j]=false;
		}
		for(const int &num:nums)
			primes[num]=false;
		for(int i=2; i<primes.size(); ++i)
			if(primes[i]) return i;
		for(int i=nums.back()+1; ; ++i){
			bool found=true;
			for(int j=2; found && j<=sqrt(i); ++j)
				if(i%j==0) found=false;
			if(found) return i;
		}
		return -1;
	}
};
